// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef BASE_NUMERICS_SAFE_MATH_IMPL_H_
#define BASE_NUMERICS_SAFE_MATH_IMPL_H_

#include <stddef.h>
#include <stdint.h>

#include <climits>
#include <cmath>
#include <cstdlib>
#include <limits>
#include <type_traits>

#include "base/numerics/safe_conversions.h"

namespace base {
namespace internal {

    // Everything from here up to the floating point operations is portable C++,
    // but it may not be fast. This code could be split based on
    // platform/architecture and replaced with potentially faster implementations.

    // Integer promotion templates used by the portable checked integer arithmetic.
    template <size_t Size, bool IsSigned>
    struct IntegerForSizeAndSign;
    template <>
    struct IntegerForSizeAndSign<1, true> {
        typedef int8_t type;
    };
    template <>
    struct IntegerForSizeAndSign<1, false> {
        typedef uint8_t type;
    };
    template <>
    struct IntegerForSizeAndSign<2, true> {
        typedef int16_t type;
    };
    template <>
    struct IntegerForSizeAndSign<2, false> {
        typedef uint16_t type;
    };
    template <>
    struct IntegerForSizeAndSign<4, true> {
        typedef int32_t type;
    };
    template <>
    struct IntegerForSizeAndSign<4, false> {
        typedef uint32_t type;
    };
    template <>
    struct IntegerForSizeAndSign<8, true> {
        typedef int64_t type;
    };
    template <>
    struct IntegerForSizeAndSign<8, false> {
        typedef uint64_t type;
    };

    // WARNING: We have no IntegerForSizeAndSign<16, *>. If we ever add one to
    // support 128-bit math, then the ArithmeticPromotion template below will need
    // to be updated (or more likely replaced with a decltype expression).

    template <typename Integer>
    struct UnsignedIntegerForSize {
        typedef typename std::enable_if<
            std::numeric_limits<Integer>::is_integer,
            typename IntegerForSizeAndSign<sizeof(Integer), false>::type>::type type;
    };

    template <typename Integer>
    struct SignedIntegerForSize {
        typedef typename std::enable_if<
            std::numeric_limits<Integer>::is_integer,
            typename IntegerForSizeAndSign<sizeof(Integer), true>::type>::type type;
    };

    template <typename Integer>
    struct TwiceWiderInteger {
        typedef typename std::enable_if<
            std::numeric_limits<Integer>::is_integer,
            typename IntegerForSizeAndSign<
                sizeof(Integer) * 2,
                std::numeric_limits<Integer>::is_signed>::type>::type type;
    };

    template <typename Integer>
    struct PositionOfSignBit {
        static const typename std::enable_if<std::numeric_limits<Integer>::is_integer,
            size_t>::type value
            = CHAR_BIT * sizeof(Integer) - 1;
    };

    // This is used for UnsignedAbs, where we need to support floating-point
    // template instantiations even though we don't actually support the operations.
    // However, there is no corresponding implementation of e.g. CheckedUnsignedAbs,
    // so the float versions will not compile.
    template <typename Numeric,
        bool IsInteger = std::numeric_limits<Numeric>::is_integer,
        bool IsFloat = std::numeric_limits<Numeric>::is_iec559>
    struct UnsignedOrFloatForSize;

    template <typename Numeric>
    struct UnsignedOrFloatForSize<Numeric, true, false> {
        typedef typename UnsignedIntegerForSize<Numeric>::type type;
    };

    template <typename Numeric>
    struct UnsignedOrFloatForSize<Numeric, false, true> {
        typedef Numeric type;
    };

    // Helper templates for integer manipulations.

    template <typename T>
    /*constexpr*/ bool HasSignBit(T x)
    {
        // Cast to unsigned since right shift on signed is undefined.
        return !!(static_cast<typename UnsignedIntegerForSize<T>::type>(x) >> PositionOfSignBit<T>::value);
    }

    // This wrapper undoes the standard integer promotions.
    template <typename T>
    /*constexpr*/ T BinaryComplement(T x)
    {
        return static_cast<T>(~x);
    }

    // Here are the actual portable checked integer math implementations.
    // TODO(jschuh): Break this code out from the enable_if pattern and find a clean
    // way to coalesce things into the CheckedNumericState specializations below.

    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_integer, T>::type
    CheckedAdd(T x, T y, RangeConstraint* validity)
    {
        // Since the value of x+y is undefined if we have a signed type, we compute
        // it using the unsigned type of the same size.
        typedef typename UnsignedIntegerForSize<T>::type UnsignedDst;
        UnsignedDst ux = static_cast<UnsignedDst>(x);
        UnsignedDst uy = static_cast<UnsignedDst>(y);
        UnsignedDst uresult = static_cast<UnsignedDst>(ux + uy);
        // Addition is valid if the sign of (x + y) is equal to either that of x or
        // that of y.
        if (std::numeric_limits<T>::is_signed) {
            if (HasSignBit(BinaryComplement(
                    static_cast<UnsignedDst>((uresult ^ ux) & (uresult ^ uy))))) {
                *validity = RANGE_VALID;
            } else { // Direction of wrap is inverse of result sign.
                *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW;
            }
        } else { // Unsigned is either valid or overflow.
            *validity = BinaryComplement(x) >= y ? RANGE_VALID : RANGE_OVERFLOW;
        }
        return static_cast<T>(uresult);
    }

    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_integer, T>::type
    CheckedSub(T x, T y, RangeConstraint* validity)
    {
        // Since the value of x+y is undefined if we have a signed type, we compute
        // it using the unsigned type of the same size.
        typedef typename UnsignedIntegerForSize<T>::type UnsignedDst;
        UnsignedDst ux = static_cast<UnsignedDst>(x);
        UnsignedDst uy = static_cast<UnsignedDst>(y);
        UnsignedDst uresult = static_cast<UnsignedDst>(ux - uy);
        // Subtraction is valid if either x and y have same sign, or (x-y) and x have
        // the same sign.
        if (std::numeric_limits<T>::is_signed) {
            if (HasSignBit(BinaryComplement(
                    static_cast<UnsignedDst>((uresult ^ ux) & (ux ^ uy))))) {
                *validity = RANGE_VALID;
            } else { // Direction of wrap is inverse of result sign.
                *validity = HasSignBit(uresult) ? RANGE_OVERFLOW : RANGE_UNDERFLOW;
            }
        } else { // Unsigned is either valid or underflow.
            *validity = x >= y ? RANGE_VALID : RANGE_UNDERFLOW;
        }
        return static_cast<T>(uresult);
    }

    // Integer multiplication is a bit complicated. In the fast case we just
    // we just promote to a twice wider type, and range check the result. In the
    // slow case we need to manually check that the result won't be truncated by
    // checking with division against the appropriate bound.
    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_integer && sizeof(T) * 2 <= sizeof(uintmax_t),
        T>::type
    CheckedMul(T x, T y, RangeConstraint* validity)
    {
        typedef typename TwiceWiderInteger<T>::type IntermediateType;
        IntermediateType tmp = static_cast<IntermediateType>(x) * static_cast<IntermediateType>(y);
        *validity = DstRangeRelationToSrcRange<T>(tmp);
        return static_cast<T>(tmp);
    }

    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed && (sizeof(T) * 2 > sizeof(uintmax_t)),
        T>::type
    CheckedMul(T x, T y, RangeConstraint* validity)
    {
        // If either side is zero then the result will be zero.
        if (!x || !y) {
            *validity = RANGE_VALID;
            return static_cast<T>(0);

        } else if (x > 0) {
            if (y > 0)
                *validity = x <= std::numeric_limits<T>::max() / y ? RANGE_VALID : RANGE_OVERFLOW;
            else
                *validity = y >= std::numeric_limits<T>::min() / x ? RANGE_VALID
                                                                   : RANGE_UNDERFLOW;

        } else {
            if (y > 0)
                *validity = x >= std::numeric_limits<T>::min() / y ? RANGE_VALID
                                                                   : RANGE_UNDERFLOW;
            else
                *validity = y >= std::numeric_limits<T>::max() / x ? RANGE_VALID : RANGE_OVERFLOW;
        }

        return static_cast<T>(x * y);
    }

    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed && (sizeof(T) * 2 > sizeof(uintmax_t)),
        T>::type
    CheckedMul(T x, T y, RangeConstraint* validity)
    {
        *validity = (y == 0 || x <= std::numeric_limits<T>::max() / y)
            ? RANGE_VALID
            : RANGE_OVERFLOW;
        return static_cast<T>(x * y);
    }

    // Division just requires a check for an invalid negation on signed min/-1.
    template <typename T>
    T CheckedDiv(T x,
        T y,
        RangeConstraint* validity,
        typename std::enable_if<std::numeric_limits<T>::is_integer,
            int>::type
        = 0)
    {
        if (std::numeric_limits<T>::is_signed && x == std::numeric_limits<T>::min() && y == static_cast<T>(-1)) {
            *validity = RANGE_OVERFLOW;
            return std::numeric_limits<T>::min();
        }

        *validity = RANGE_VALID;
        return static_cast<T>(x / y);
    }

    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed,
        T>::type
    CheckedMod(T x, T y, RangeConstraint* validity)
    {
        *validity = y > 0 ? RANGE_VALID : RANGE_INVALID;
        return static_cast<T>(x % y);
    }

    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
        T>::type
    CheckedMod(T x, T y, RangeConstraint* validity)
    {
        *validity = RANGE_VALID;
        return static_cast<T>(x % y);
    }

    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed,
        T>::type
    CheckedNeg(T value, RangeConstraint* validity)
    {
        *validity = value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW;
        // The negation of signed min is min, so catch that one.
        return static_cast<T>(-value);
    }

    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
        T>::type
    CheckedNeg(T value, RangeConstraint* validity)
    {
        // The only legal unsigned negation is zero.
        *validity = value ? RANGE_UNDERFLOW : RANGE_VALID;
        return static_cast<T>(
            -static_cast<typename SignedIntegerForSize<T>::type>(value));
    }

    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed,
        T>::type
    CheckedAbs(T value, RangeConstraint* validity)
    {
        *validity = value != std::numeric_limits<T>::min() ? RANGE_VALID : RANGE_OVERFLOW;
        return static_cast<T>(std::abs(value));
    }

    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
        T>::type
    CheckedAbs(T value, RangeConstraint* validity)
    {
        // T is unsigned, so |value| must already be positive.
        *validity = RANGE_VALID;
        return value;
    }

    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_integer && std::numeric_limits<T>::is_signed,
        typename UnsignedIntegerForSize<T>::type>::type
    CheckedUnsignedAbs(T value)
    {
        typedef typename UnsignedIntegerForSize<T>::type UnsignedT;
        return value == std::numeric_limits<T>::min()
            ? static_cast<UnsignedT>(std::numeric_limits<T>::max()) + 1
            : static_cast<UnsignedT>(std::abs(value));
    }

    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_integer && !std::numeric_limits<T>::is_signed,
        T>::type
    CheckedUnsignedAbs(T value)
    {
        // T is unsigned, so |value| must already be positive.
        return static_cast<T>(value);
    }

// These are the floating point stubs that the compiler needs to see. Only the
// negation operation is ever called.
#define BASE_FLOAT_ARITHMETIC_STUBS(NAME)                               \
    template <typename T>                                               \
    typename std::enable_if<std::numeric_limits<T>::is_iec559, T>::type \
        Checked##NAME(T, T, RangeConstraint*)                           \
    {                                                                   \
        NOTREACHED();                                                   \
        return static_cast<T>(0);                                       \
    }

    BASE_FLOAT_ARITHMETIC_STUBS(Add)
    BASE_FLOAT_ARITHMETIC_STUBS(Sub)
    BASE_FLOAT_ARITHMETIC_STUBS(Mul)
    BASE_FLOAT_ARITHMETIC_STUBS(Div)
    BASE_FLOAT_ARITHMETIC_STUBS(Mod)

#undef BASE_FLOAT_ARITHMETIC_STUBS

    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedNeg(
        T value,
        RangeConstraint*)
    {
        return static_cast<T>(-value);
    }

    template <typename T>
    typename std::enable_if<std::numeric_limits<T>::is_iec559, T>::type CheckedAbs(
        T value,
        RangeConstraint*)
    {
        return static_cast<T>(std::abs(value));
    }

    // Floats carry around their validity state with them, but integers do not. So,
    // we wrap the underlying value in a specialization in order to hide that detail
    // and expose an interface via accessors.
    enum NumericRepresentation {
        NUMERIC_INTEGER,
        NUMERIC_FLOATING,
        NUMERIC_UNKNOWN
    };

    template <typename NumericType>
    struct GetNumericRepresentation {
        static const NumericRepresentation value = std::numeric_limits<NumericType>::is_integer
            ? NUMERIC_INTEGER
            : (std::numeric_limits<NumericType>::is_iec559 ? NUMERIC_FLOATING
                                                           : NUMERIC_UNKNOWN);
    };

    template <typename T, NumericRepresentation type = GetNumericRepresentation<T>::value>
    class CheckedNumericState {
    };

    // Integrals require quite a bit of additional housekeeping to manage state.
    template <typename T>
    class CheckedNumericState<T, NUMERIC_INTEGER> {
    private:
        T value_;
        RangeConstraint validity_ : CHAR_BIT; // Actually requires only two bits.

    public:
        template <typename Src, NumericRepresentation type>
        friend class CheckedNumericState;

        CheckedNumericState()
            : value_(0)
            , validity_(RANGE_VALID)
        {
        }

        template <typename Src>
        CheckedNumericState(Src value, RangeConstraint validity)
            : value_(static_cast<T>(value))
            , validity_(GetRangeConstraint(validity | DstRangeRelationToSrcRange<T>(value)))
        {
            static_assert(std::numeric_limits<Src>::is_specialized,
                "Argument must be numeric.");
        }

        // Copy constructor.
        template <typename Src>
        CheckedNumericState(const CheckedNumericState<Src>& rhs)
            : value_(static_cast<T>(rhs.value()))
            , validity_(GetRangeConstraint(
                  rhs.validity() | DstRangeRelationToSrcRange<T>(rhs.value())))
        {
        }

        template <typename Src>
        explicit CheckedNumericState(
            Src value,
            typename std::enable_if<std::numeric_limits<Src>::is_specialized,
                int>::type
            = 0)
            : value_(static_cast<T>(value))
            , validity_(DstRangeRelationToSrcRange<T>(value))
        {
        }

        RangeConstraint validity() const { return validity_; }
        T value() const { return value_; }
    };

    // Floating points maintain their own validity, but need translation wrappers.
    template <typename T>
    class CheckedNumericState<T, NUMERIC_FLOATING> {
    private:
        T value_;

    public:
        template <typename Src, NumericRepresentation type>
        friend class CheckedNumericState;

        CheckedNumericState()
            : value_(0.0)
        {
        }

        template <typename Src>
        CheckedNumericState(
            Src value,
            RangeConstraint validity,
            typename std::enable_if<std::numeric_limits<Src>::is_integer, int>::type = 0)
        {
            switch (DstRangeRelationToSrcRange<T>(value)) {
            case RANGE_VALID:
                value_ = static_cast<T>(value);
                break;

            case RANGE_UNDERFLOW:
                value_ = -std::numeric_limits<T>::infinity();
                break;

            case RANGE_OVERFLOW:
                value_ = std::numeric_limits<T>::infinity();
                break;

            case RANGE_INVALID:
                value_ = std::numeric_limits<T>::quiet_NaN();
                break;

            default:
                NOTREACHED();
            }
        }

        template <typename Src>
        explicit CheckedNumericState(
            Src value,
            typename std::enable_if<std::numeric_limits<Src>::is_specialized,
                int>::type
            = 0)
            : value_(static_cast<T>(value))
        {
        }

        // Copy constructor.
        template <typename Src>
        CheckedNumericState(const CheckedNumericState<Src>& rhs)
            : value_(static_cast<T>(rhs.value()))
        {
        }

        RangeConstraint validity() const
        {
            return GetRangeConstraint(value_ <= std::numeric_limits<T>::max(),
                value_ >= -std::numeric_limits<T>::max());
        }
        T value() const { return value_; }
    };

    // For integers less than 128-bit and floats 32-bit or larger, we have the type
    // with the larger maximum exponent take precedence.
    enum ArithmeticPromotionCategory { LEFT_PROMOTION,
        RIGHT_PROMOTION };

    template <typename Lhs,
        typename Rhs = Lhs,
        ArithmeticPromotionCategory Promotion = (MaxExponent<Lhs>::value > MaxExponent<Rhs>::value)
            ? LEFT_PROMOTION
            : RIGHT_PROMOTION>
    struct ArithmeticPromotion;

    template <typename Lhs, typename Rhs>
    struct ArithmeticPromotion<Lhs, Rhs, LEFT_PROMOTION> {
        typedef Lhs type;
    };

    template <typename Lhs, typename Rhs>
    struct ArithmeticPromotion<Lhs, Rhs, RIGHT_PROMOTION> {
        typedef Rhs type;
    };

    // We can statically check if operations on the provided types can wrap, so we
    // can skip the checked operations if they're not needed. So, for an integer we
    // care if the destination type preserves the sign and is twice the width of
    // the source.
    template <typename T, typename Lhs, typename Rhs>
    struct IsIntegerArithmeticSafe {
        static const bool value = !std::numeric_limits<T>::is_iec559 && StaticDstRangeRelationToSrcRange<T, Lhs>::value == NUMERIC_RANGE_CONTAINED && sizeof(T) >= (2 * sizeof(Lhs)) && StaticDstRangeRelationToSrcRange<T, Rhs>::value != NUMERIC_RANGE_CONTAINED && sizeof(T) >= (2 * sizeof(Rhs));
    };

} // namespace internal
} // namespace base

#endif // BASE_NUMERICS_SAFE_MATH_IMPL_H_
